package cn.lccabc.dichotomy.no0367;

/**
 * @program: leet-code
 * @description:
 * 给定一个正整数 num，编写一个函数，如果 num 是一个完全平方数，则返回 True，否则返回 False。
 *
 * 说明：不要使用任何内置的库函数，如  sqrt。
 *
 * 示例 1：
 *
 * 输入：16
 * 输出：True
 * 示例 2：
 *
 * 输入：14
 * 输出：False
 *
 * @author: LiCC
 * @create: 2020-02-25 20:39
 */
public class Solution {

    public static boolean isPerfectSquare(int num) {
        // 牛顿迭代法
        if (num < 2) return true;
        int x0 = num;
        int x1 = (x0 + num / x0) / 2;
        while (Math.abs(x0 - x1) >= 1){
            x0 = x1;
            x1 = (x0 + num / x0) / 2;
        }
        return num == (x1 * x1);

        // 二分法
//        if(num < 2) return true;
//        long left = 2, right = num / 2, mid, guessSquared;
//        while (left <= right){
//            mid = left + (right - left) / 2;
//            guessSquared = mid * mid;
//            System.out.println(mid);
//            if (num == guessSquared) {
//                return true;
//            }
//            if (num < guessSquared){
//                right = mid - 1;
//            } else {
//                left = mid + 1;
//            }
//        }
//        return false;
    }

    public static void main(String[] args) {
        int num = 808201;
        boolean result = isPerfectSquare(num);
        System.out.println(result);
    }
}
